public class Day7 {
    //329.矩阵中的最长递增序列
    int m,n;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    int[][] memo;
    public int longestIncreasingPath(int[][] matrix) {
        m=matrix.length;n=matrix[0].length;
        memo = new int[m][n];
        int ret = 0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                ret = Math.max(dfs(matrix,i,j),ret);
            }
        }
        return ret;
    }
    public int dfs(int[][] nums,int i,int j) {
        if(memo[i][j] != 0) {
            return memo[i][j];
        }
        int ret = 1;
        for(int k=0;k<4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x>=0&&x<m&&y>=0&&y<n && nums[x][y]>nums[i][j]) {
                ret = Math.max(ret,dfs(nums,x,y)+1);
            }
        }
        memo[i][j]=ret;
        return ret;
    }
}
